Not Applicable
A microfiche appendix is attached. The total number of microfiche is one and the total number of frames is ninety-two.
All of the material in this patent document is subject to copyright protection under the copyright laws of the United States and of other countries. The owner of the copyright has no objection to the facsimile reproduction by anyone of the patent document or the patent disclosure, as it appears in the United States Patent and Trademark Office file or records, but otherwise reserves all copyrights whatsoever.
1. Field of the Invention
This invention pertains generally to network server technology, and more particularly to a pseudo-serving system and method for reducing congestion at the server or within the network itself. The pseudo-serving mechanisms of the invention provide a means of cooperatively sharing the burden of file serving within the body of Internet requesters. Contract based incentives and security features operate to persuade resource consumers to help serve resources in return for speedier data access.
2. Description of the Background Art
The phenomenal growth of interconnected computer networks such as the Internet has intensified the demand for bandwidth. A major cause of delays in computer networks is congestion which, in the context of data transmission, is conceptually similar to congestion on a freeway. Each data packet to be passed over the network can be likened to a vehicle that is heading to a destination. When too many data packets (cars) are heading to destinations that lie along the same internet segment (freeway), then these packets (cars) interfere with one another. This causes the speed of the traffic to slow down, and it takes longer for the data packets (cars) to reach their desired destinations.
Bandwidth congestion in a computer network occurs largely at three different locations within the network, which can be categorized as follows:
(a) Server-side (on-ramp)xe2x80x94The bandwidth of the server and its link to the Internet is divided among the clients downloading files from the server. While the user can cause tremendous data to flow, the server and/or its link to the lnternet is a point of congestion;
(b) Intermediate links (sections of freeway)xe2x80x94Congestion arises in the intermediate nodes and links of the Internet because too many users are using the network at the same time and the user requests share a common node or link. For example, congestion occurs when a router can not route packets faster than they arrive; and
(c) Client-side (off-ramp)xe2x80x94The bandwidth provided by the user""s internet service provider (ISP) is shared among a large number of other users (user community). The greater the sharing, the less bandwidth each user receives.
To better meet the demand for bandwidth and reduce Internet congestion, the research community is responding with innovative approaches. One approach, for example, is the development of faster network components, including modems, switches, and transmission lines. Despite these improvements, however, new multimedia applications continue to demand ever-greater bandwidth. The transmission of real-time traffic such as is required for Internet phone and videoconferencing applications, as well as the download of large Moving Picture Experts Group (MPEG) files, is tolerable only under the best of network conditions.
Another approach is the development of new protocols that use bandwidth more efficiently. Examples include Compressed Serial Line Internet Protocol (CSLIP) and Low-Bandwidth X, which use compression techniques to reduce redundancy. Other protocols such as Hyper-Text Transfer Protocol version 1.1 (HTTP 1.1) and Transaction Transmission Control Protocol (TTCP) improve on current standards by removing overhead. Still others call for the removal of entire protocol layers. Work is underway, for example, to implement Transmission Control Protocol/Internet Protocol (TCP/IP) directly over a Synchronous Optical Network (SONET).
A further approach is the development of caching mechanisms within the Internet. These schemes work by recognizing that files are often requested more than once. By storing popular files locally, future requests for these files can be satisfied quickly without the need to retrieve them from the server.
Caching schemes are characterized along a number of dimensions. Two of the most important ones include the location of the cache and the degree of cooperation. Data transfers from a cache close to the client tend to be faster and demand fewer resources from the network. Cooperative caches generally have fewer cache misses than those that operate by themselves. Although caching schemes work well and are responsible for a portion of the reduction of bandwidth usage today, they are not always able to satisfy requests. This happens when the request is a first request for the data, and when the requested data in the cache has become xe2x80x9cstalexe2x80x9d; in either case, the data must be retrieved from the server. Moreover, cooperative caches that yield higher hit rates suffer from many of the same problems that they were intended to address. These include bottlenecks at certain xe2x80x9chot spotsxe2x80x9d (sometimes retrieving a file from a heavily loaded cache is slower than retrieving it directly from the server) and increased latencies because the cache is located many nodes (xe2x80x9chopsxe2x80x9d) away from the client.
Closely related to caching is prefetching. Rather than keeping retrieved data locally on behalf of future requests, prefetching works by transferring data to the user prior to a user request. Mailing lists, network news, and so-called xe2x80x9cpushxe2x80x9d technologies belong to this category; data is pushed from the server to the client in anticipation of future requests. Unfortunately, prefetching suffers from two important drawbacks. First, it is useless to the user if the file requested has not been prefetched. Second, it generates unnecessary traffic in the network whenever files are retrieved for which there was never a request. This further exacerbates congestion in the network without providing any benefits.
Still another approach utilizes basic principles of economics. It recognizes that bandwidth is a scarce resource and seeks ways to allocate it optimally. Work in this area is often concerned with maximizing the welfare of the user community. This is usually done by granting priority for the delivery of packets to users who value it more at the expense of those who value it less. To encourage the truthful revelation of user values, these schemes often institute some form of pricing based on usage of bandwidth. Mackie-Mason and Varian""s xe2x80x9csmart marketxe2x80x9d gives a flavor for how economics can be applied to the allocation of bandwidth. In it, packets are routed based on bids placed by users; packets with higher bids are routed with higher priority over ones with lower bids. While schemes like the smart market maximize the welfare of the user community, they tend to be impractical from a number of standpoints. Prioritizing packets based on bids, for example, requires that all routers cooperate. This requires significant changes to the well-entrenched IP protocol and is therefore difficult to implement. Moreover, pricing schemes based on usage often incur significant accounting costs, and basic questions such as who should be billed in various distributed connectionless environment, such as the Internet, are difficult to answer.
The development of faster network components and more efficient protocols act to directly reduce network congestion, while caching and prefetching schemes may act to reduce congestion, but are not always effective. For example, requests that do not xe2x80x9chitxe2x80x9d the caches go directly to the server. With a cache hit rate of about 50%, even with cooperative caches roughly half of all requests still arrive at the server. These cache misses apply both to regular caches and to cooperative caches.
Therefore a need exists for a technology that improves the efficiency of existing internet server resources that can be easily implemented on the existing internet infrastructure and does not rely on the hit-or-miss nature of caching. The present invention satisfies that need, as well as others, and overcomes deficiencies in current approaches.
The present invention pertains to a method for reducing server side and intermediate link congestion for those requests which are not intercepted by the caches in a cached data transmission system and which would otherwise arrive at the server. In general terms our method, which we refer to as xe2x80x9cpseudo-servingxe2x80x9d, improves the efficiency of existing Internet server resources by the cooperative sharing of retained resources within the normal body of requesters.
In accordance with an aspect of the invention, pseudo-serving provides another solution to the bandwidth problem by combining concepts from both the caching approach and the economics approach. Pseudo-serving is fundamentally based on the observation that users in possession of popular files from a busy server are in possession of a valuable resource. If they can be convinced to share this resource, congestion near the server and at the intermediate links can be avoided, and the overall welfare of the user community would be enhanced. In the description herein the term xe2x80x9cuserxe2x80x9d or xe2x80x9cuser requestxe2x80x9d infers the inclusion of xe2x80x9cproxiesxe2x80x9d and xe2x80x9cproxy requestsxe2x80x9d on behalf of a user. Pseudo-serving provides the necessary incentives for users to share files according to a xe2x80x9ccontractxe2x80x9d. In it, the server agrees to provide information on where the requested file may be immediately obtained. In exchange, the client agrees to xe2x80x9cpayxe2x80x9d by serving the retrieved file to a specified number of other users within a specified period of time. This payment is used to satisfy requests for this same data by other users.
In accordance with another aspect of the invention, a user participates in pseudo-serving by joining as a xe2x80x9cpseudo-serverxe2x80x9d in a pseudo-serving system. A pseudo-serving system according to the present invention comprises two components: a super-server and a set of pseudo-servers. A pseudo-server can be hosted within a traditional server or within a user workstation that shares files. The super-server grants the pseudo-server access concessions to resources in exchange for some amount of network and storage resources through the contract. The super-server can grant access concessions to any resource over which it has control. In the usual case these resources are files, but the resource could comprise a program with data, or any alternate network resource for which a requester may desire access concessions. In determining what constitutes an acceptable exchange of services for access concessions, the network conditions are interpreted in regard to policy set by the system administrator. The amount of resources that must be must be given in return for an access concession may be zero under xe2x80x9clow-demandxe2x80x9d conditions, when the superserver functions as a concurrent server and the pseudo-servers function as clients. Under xe2x80x9chigh-demandxe2x80x9d conditions, when the downloading files take a long time due to congestion in the network, it may be possible to improve the pseudo-server""s access to the requested file in exchange for temporary usage of the pseudo-server""s network and storage resources. Under these circumstances, and subject to the condition that the contract is met, the super-server gives the pseudo-server a list of referrals to where the requested data may be obtained.
In general, any network environment can employ the pseudo-serving method of sharing the burden of resource serving embodied in this inventive system and method. Pseudo-serving offers a number of advantages, including:
Self-scalingxe2x80x94In pseudo-serving, information consumers become information providers through a bartering system. Under this mechanism, resources are generated quickly and dynamically to meet demand;
End-to-endxe2x80x94A pseudo-server system assumes provision of an end-to-end service, such as that provided by today""s Internet. No changes need to be made in the underlying network infrastructure for pseudo-serving to work effectively, although it can exploit additional network services to enhance performance. For example, future networks that provide topological information can be used by a pseudo-server system to make better referrals;
Central-controlxe2x80x94The super-server controls the distribution of its information through referrals. Important control information is sent directly from the server to the client while bandwidth-intensive data is sent by the pseudo-servers. This is an important feature for information providers that want to distribute information to as large an audience as possible without sacrificing fine-grained control of access to their information. For example, using pseudo-serving, information providers can distribute bandwidth-intensive multimedia files to a much larger audience, at significantly reduced costs compared to existing schemes, while maintaining a fine-grained profile of the count of the number of users in actual possession of the files. This is in contrast to caching schemes, which hide client requests from the server;
Fault-tolerancexe2x80x94Pseudo-serving is robust due to the exponential nature by which the pool of pseudo-servers grows. Simulations show pseudo-serving to be effective even if 40% of the users breach their contracts;
Orthogonal to existing schemesxe2x80x94Pseudo-serving is orthogonal to existing schemes for reducing response time. With respect to the operation of caching schemes, for example, pseudo-serving plays the role of a xe2x80x9ccatch-allxe2x80x9d; requests not intercepted by caches are serviced by pseudo-server systems;
Easy to deployxe2x80x94The two components of the pseudo-server system, the super-server, and the pseudo-server can be easily deployed in today""s Internet; and
Reservationxe2x80x94To the extent that contracts are honored, pseudo-serving is a reservation scheme: requested files are guaranteed to reside in the referred pseudo-servers. This is in contrast to caching schemes, where effectiveness depends on the hit rate of the cache.
An object of the invention is to allow the user or a proxy working on behalf of the user to bypass certain types of congestion in the Internet with the goal of reducing the user""s response time.
An object of the invention is to reduce network response times for users that cooperate with the pseudo-serving environment.
Another object the invention is to improve the utility of network resources by enticing information consumers to become information providers by means of a bartering system, whereby the serving of data resources can more effectively meet demand.
Another object the invention is to improve the end-to-end service accorded a user without a requisite need to make fundamental infrastructure changes to the underlying network over which the invention operates.
Another object the invention is to provide servers with an ability to control the distribution of information through a mechanism of referrals, whereby the server can decide whether the requested data is to be served directly or is to be served indirectly by a pseudo-server, and may influence the decision by the user through the use of the referral mechanism.
Another object the invention is to provide a mechanism that reduces the burden on congested servers that can operate despite abuses and noncompliance within the network community.
Another object the invention is to provide a mechanism that reduces the burden on congested servers that is interoperable with various existing schemes, such as caching, that reduce response times.
Another object the invention is to provide a mechanism that reduces the burden on congested servers that is easy to deploy on an existing network.
Another object the invention is to provide a mechanism that reduces the burden on congested servers that incorporates a reservation mechanism, whereby to the extent that contracts are honored, the requested files are guaranteed to reside in the referred pseudo-servers. The mechanism does not rely on a cache xe2x80x9chit ratexe2x80x9d that is dependent on cache use and loss through periodic cache flushing.
Further objects and advantages of the invention will be brought out in the following portions of the specification, wherein the detailed description is for the purpose of fully disclosing preferred embodiments of the invention without placing limitations thereon.